package DynamicProgramming;

public class _343_IntegerBreak {
    public int integerBreak(int n) {
        if(n==0) return 1;
        int[] dp = new int[n + 1];
        //initial dp values
        for (int i = 3; i <= n; i++) {
            dp[i] = i - 1;
        }
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            int start = 1, end = i - 1;
            while (start <= end) {
                dp[i] = Math.max(dp[i], start * end);
                dp[i] = Math.max(dp[i], dp[start] * end);
                dp[i] = Math.max(dp[i], dp[start] * dp[end]);
                dp[i] = Math.max(dp[i], (start) * dp[end]);
                start++;
                end--;
            }
        }
        return dp[n];
    }
}
